package com.leo.algorithm.链表;

import java.util.Stack;

/**
 * 链表反转 1->2->3 得到 3->2->1
 */
public class ReverseNode {
    
    public class  Node{
        private int val;
        private Node next;

        public Node(){
            this(0);
        }
        public Node(int val){
            this.val=val;
        }
    }

    public Node reverse(Node node){
      if(node==null || node.next==null){
          return node;
      }
        Node temp = node.next;
        Node reverse = reverse(node.next);
        temp.next=node;
        node.next=null;
        return reverse;
    }

    public Node reverseNR(Node node){
        Stack<Node>stackNode=new Stack<>();
        Node reNode=node;
        while(reNode!=null){
           stackNode.push(reNode);
           reNode=reNode.next;
       }

        Node root =new Node();
        Node parent=root;
        while(!stackNode.empty()){
            Node item =stackNode.pop();
            item.next=null;
            parent.next=item;
            parent=item;
       }

        return root.next;
    }

    public static void main(String[] args) {
        ReverseNode reverseNode=new ReverseNode();
        Node node = reverseNode.new Node(1);
        Node node1 = reverseNode.new Node(2);
        Node node2 = reverseNode.new Node(3);
        node.next=node1;
        node1.next=node2;
        Node reverse = reverseNode.reverseNR(node);
       while(reverse!=null){
           System.out.println(reverse.val);
           reverse=reverse.next;
       }
    }
}
